/***************************************************************************
 *   Copyright (C) 2006 2007 2008by ywchen2000                         *
 *   ywchen2000@gmail.com                                                         *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include"tree.h"
#include<QtDebug>
tree::tree(QWidget* parent):QWidget(parent),head(NULL),treearray(NULL)
{
}
tree::~tree(void)
{
	close();
}
void tree::close(void)
{
	for(register int i=0;i<mSize;i++)
	{
		if(treearray[i]==NULL)
			continue;
		if(!treearray[i]->value.isNull())
			deletetree(treearray[i]);									        }
 	delete[] treearray;
}

void tree::deletetree(nodeprivate* node)
{
	if(node==NULL)
		return ;
	deletetree(node->left);
	deletetree(node->right);
	delete node;
}
void tree::insert(const QString& text)
{
	if(text.isNull() || text.isEmpty())
	{
		return ;
	}
	/*
          text contain file path and file name,hash file name so that find a slot,insert
	  text to the slot
         */
         //filename will be inserted
        QFileInfo filename(text);
	char* buffer=const_cast<char*>(filename.fileName().toStdString().c_str());
	int hashkey=ELFhash(buffer);
	if(treearray[hashkey]->value.isNull())
	{
		treearray[hashkey]->value=text;
		return ;
	}
	else
	{
		nodeprivate* currnode;
		currnode=head=treearray[hashkey];
		while(currnode!=NULL)
		{
			QFileInfo fileinfo(currnode->value);
			int result=QString::compare(fileinfo.fileName(),filename.fileName());
			if(result==0)
			{
				nodeprivate* newnode=new nodeprivate(text);
				newnode->left=currnode->left;
				currnode->left=newnode;	
				return;
			}
			else if(result<0)
			{
				if(currnode->left==NULL)
				{
					currnode->left=new nodeprivate(text);
					return ;
                                 }
				else
					currnode=currnode->left;		
			}
			else
			{
				if(currnode->right==NULL)
				{
					currnode->right=new nodeprivate(text);
					return ;
				}
				else
					currnode=currnode->right;
			}	
		}
	}
}
int tree::ELFhash(char *key)
{
  /*
	unsigned long h=0, g;
	while (*key)
	{
		h = (h<<4)+(*key++);
		g = h & 0xf0000000L;
		if (g) h ^= g>>24;
		h &= ~g;
	}
	return h%mSize;
   */
    int asc=*key;
    return asc%mSize;
} 
bool tree::init(void)
{
	treearray=new nodeprivate* [mSize];
	if(treearray==NULL)
	{
		printf("out of memory\n");
		return false;
        }
	for(register int i=0;i<mSize;i++)
	{
		treearray[i]=new nodeprivate();
		if(treearray[i]==NULL)
		{
			printf("out of memory\n");
			return false;
		}
	}
	return true;
}
void tree::show_all(QListWidget* l)
{
	for(register int i=0;i<mSize;i++)
	{
		if(!treearray[i]->value.isEmpty() || !treearray[i]->value.isNull())
		{
			display_result(treearray[i],l);
		}
	}	
}

void tree::display_result(nodeprivate* node,QListWidget* l)
{
	if(node==NULL)
		return ;
	l->addItem(node->value);
	display_result(node->left,l);
	display_result(node->right,l);		
}
bool tree::find(const QString& text,QListWidget* l)
{
	if(text.isNull() || text.isEmpty())
	{
		return false;
	}
	char* buffer=const_cast<char*>(text.toStdString().c_str());
	int hashkey=ELFhash(buffer);
	if(treearray[hashkey]->value.isNull())
		return false;
	nodeprivate*  currnode=treearray[hashkey];
	while(currnode!=NULL)
	{
		//head->value
                QFileInfo fileinfo(currnode->value);
		QString str=fileinfo.fileName();
		bool bool_result=str.startsWith(text);
		if(bool_result)
		{
			l->clear();
			display_result(currnode,l);
			return true;
		}
		int result=QString::compare(str,text);
		if(result==0)
		{	
			l->clear();
			display_result(currnode,l);
			return true;
		}
		else if(result<0)
		{
			currnode=currnode->left;		
		}
		else
		{
			currnode=currnode->right;
		}	
	}
	return false;
}

void tree::FindFileRec(const nodeprivate* node,const QString& Text,QStringList& StrList)
{
	if(node == NULL)
		return ;
        QFileInfo fileinfo(node->value);
	if(Text == fileinfo.fileName())
		StrList.append(node->value);
	FindFileRec(node->left,Text,StrList);
	FindFileRec(node->right,Text,StrList);
}

QStringList tree::find(const QString& text)
{
	QStringList FileList;
	if(text.isNull() || text.isEmpty())
	{
		return FileList;
	}
	char* buffer=const_cast<char*>(text.toStdString().c_str());
	int hashkey=ELFhash(buffer);
	if(treearray[hashkey]->value.isNull())
		return FileList;

	nodeprivate*  currnode=treearray[hashkey];
	while(currnode!=NULL)
	{
                QFileInfo fileinfo(currnode->value);
		QString str=fileinfo.fileName();
		int result=QString::compare(str,text);
		if(result==0)
		{	
			FindFileRec(currnode,text,FileList);
			return FileList;
		}
		else if(result<0)
		{
			currnode=currnode->left;		
		}
		else
		{
			currnode=currnode->right;
		}	
	}
}
